<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    // 封装双向链表
    function DoublyLinkedList(data) {
        // 内部类 : 节点类
        function Node(data) {
            this.data = data
            this.prev = null
            this.next = null
        }

        // 属性
        this.head = null
        this.tail = null
        this.length = 0

        // 需要的操作：方法
        //1. append方法
        DoublyLinkedList.prototype.append = function (data) {
            // 1. 根据data创建节点
            var newNode = new Node(data)

            // 2.判断是否为第一个节点
            if (this.length == 0) {
                this.head = newNode
                this.tail = newNode
            } else {
                newNode.prev = this.tail
                this.tail.next = newNode
                this.tail = newNode
            }

            // length + 1
            this.length += 1
        }

        // 2.将链表转化为字符串形式
        // 2.1.toString方法
        DoublyLinkedList.prototype.toString = function () {
            return this.backwardString()
        }


        // 2.2.forwardString方法 从后往前
        DoublyLinkedList.prototype.forwardString = function () {
            // 1.定义变量
            var current = this.tail
            var resultString = ""

            // 2.依次向前遍历，获取每一个节点
            while (current) {
                resultString += current.data + " "
                current = current.prev
            }

            return resultString

        }


        // 2.3.backwardString方法 从前到后
        DoublyLinkedList.prototype.backwardString = function () {
            // 1.定义变量
            var current = this.head
            var resultString = ""

            // 2.依次向后遍历，获取每一个节点
            while (current) {
                resultString += current.data + " "
                current = current.next
            }

            return resultString
        }


        // 3. insert方法
        DoublyLinkedList.prototype.insert = function (position, data) {
            // 1.越界判断
            if (position < 0 || position > this.length) return false

            // 2.根据data创建新的节点
            var newNode = new Node(data)

            // 3.判断原来的列表是否为空
            if (this.head == 0) {
                this.head = newNode
                this.tail = newNode
            } else {
                // 3.1.判断position是否为0
                if (position == 0) {
                    this.head.prev = newNode
                    newNode.next = this.head
                    this.head = newNode
                } else if (position == this.length) {
                    this.tail.next = newNode
                    newNode.prev = this.tail
                    this.tail = newNode
                } else {
                    var current = this.head
                    var index = 0

                    while (index++ < position) {
                        current = current.next
                    }

                    newNode.next = current
                    newNode.prev = current.prev
                    current.prev.next = newNode
                    current.prev = newNode
                }
            }
            // 4.length+1
            this.length += 1

            return true

        }

        // 4. get方法
        DoublyLinkedList.prototype.get = function (position) {
            // 1.越界判断
            if (position < 0 || position >this.length) return null

            // 2.获取元素
            var current = this.head
            var index = 0

            while (index++ < position) {
                current = current.next
            }

            return current.data

        }


        // 5.indexOf方法
        DoublyLinkedList.prototype.indexOf = function (data) {
            // 1.定义变量
            var current = this.head
            var index = 0

            // this.length / 2 > position 从前往后遍历
            // this.length / 2 < position 从后往前遍历

            // 2.查找和data相同的节点
            while (current) {
                if (current.data == data) {
                    return index
                }
                current = current.next
                index += 1
            }

            return -1
        }


        // 6.update方法
        DoublyLinkedList.prototype.update = function (position, newData) {
            // 1.越界判断
            if (position < 0 || position >= this.length) return false

            // 2.寻炸正确的节点
            var current = this.head
            var index = 0
            while (index++ < position) {
                current = current.next
            }
            current.data = newData
            return true

        }


        // removeAt方法
        DoublyLinkedList.prototype.removeAt = function (position) {
            // 1.越界判断
            if (position < 0 || position >= this.length) return false

            // 2.判断是否只有一个节点
            var current = this.head
            if (this.length == 1) {
                this.head = null
                this.head = null
            }else {
                    if (position == 0) {
                    this.head.next.prev = null
                    this.head = this.head.next
                } else if (position == this.length - 1) {
                    current = this.tail
                    this.tail.prev.next = null
                    this.tail = this.tail.prev
                } else {
                    var index = 0
                    while (index++ < position) {
                        current = current.next
                    }
                    current.prev.next = current.next
                    current.next.prev = current.prev
                }
            }
            // length - 1
            this.length -= 1
            return current.data
        }

        // 8.remove方法
        DoublyLinkedList.prototype.remove = function (data) {
            // 1.根据data获取下标值
            var index = this.indexOf(data)

            //2.根据index删除对应的节点
            return this.removeAt(index)

        }

        // 9.isEmpty方法
        DoublyLinkedList.prototype.isEmpty = function () {
            return this.length == 0
        }

        // 10.size方法
        DoublyLinkedList.prototype.size = function () {
            return this.length
        }

        // 11.获取链表的第一个元素
        DoublyLinkedList.prototype.getHead = function () {
            return this.head.data
        }

        // 12.获取链表最后一个元素
        DoublyLinkedList.prototype.getTail = function () {
            return this.tail.data
        }

    }

    // 测试代码
    var list = new DoublyLinkedList()

    // 1.测试append方法
    list.append('123')
    list.append('456')
    list.append('789')
    alert(list)

    // 2.测试转成字符串的方法
    // alert(list.backwardString())
    // alert(list.forwardString())
    // alert(list.toString())

    // 3.测试insert方法
    list.insert(0, 'aaa')
    list.insert(4, 'bbb')
    list.insert(2, 'ccc')
    alert(list)

    // 4.测试get方法
    // alert(list.get(0))
    // alert(list.get(2))
    // alert(list.get(5))

    // 5.测试indexOf方法
    // alert(list.indexOf('aaa'))
    // alert(list.indexOf('bbb'))
    // alert(list.indexOf('ccc'))

    // 6.测试updata方法
    list.update(0, 'mmm')
    list.update(1, 'nnn')
    alert(list)

    // 7.测试removeAt方法
    alert(list.removeAt(1))
    alert(list.removeAt(0))
    alert(list)

    // 8.测试remove方法
    alert(list.remove('ccc'))
    alert(list)

    // 9.测试其他方法
    alert(list.isEmpty())
    alert(list.size())
    alert(list.getHead())
    alert(list.getTail())

</script>
</body>
</html>
